#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param A: an integer ratated sorted array and duplicates are allowed
    @param target: An integer
    @return: a boolean
    """
    def search(self, A, target):
        # write your code here
        min_idx = self.find_min_idx(A)

        exist_idx1 = self.search_interval(A, target, 0, min_idx-1)
        if exist_idx1 is None:
            return not self.search_interval(A, target, min_idx, len(A)-1) is None
        else:
            return True

    def search_interval(self, A, target, left, right):
        if not A:
            return None

        while left <= right:
            medium = (left + right) // 2
            med_v = A[medium]
            if target == med_v:
                return medium

            if target > med_v:
                left = medium + 1
            else:
                right = medium - 1

        return None

    def find_min_idx(self, nums):
        # write your code here
        if not nums:
            return -1

        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            # print(left, mid, right)
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] <= nums[right]:
                right = mid

        return right


def main():
    print("start main")

if __name__ == "__main__":
    main()
